/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package reiniciotsp;

import java.util.Vector;
import lectorArchivos.Problema;

/**
 *
 * @author gabula
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Problema lp = new Problema("src\\optimizacion\\resources\\berlin52.tsp");
        double[][] dist = lp.getDistancias();
        int numero_nodos = lp.getNumNodos();
        int[] solucion = new int[numero_nodos];
        Vector nodos = new Vector();
        for (int i = 0; i < numero_nodos; i++) {
            nodos.add((i + 1));
        }
        int ii = 0;
        while (nodos.size() > 0) {
            int pos = (int) Math.floor(Math.random() * nodos.size());
            solucion[ii] = Integer.parseInt(nodos.get(pos).toString());
            nodos.remove(pos);
            System.out.print(solucion[ii] + " ");
            ii++;
        }
        System.out.println("");
        double distancia = 0;
        for (int j = 0; j < solucion.length - 1; ++j) {
            distancia += dist[solucion[j] - 1][solucion[j + 1] - 1];
        }
        distancia += dist[solucion[solucion.length - 1] - 1][solucion[0] - 1];
        System.out.println("Distancia =" + distancia);
        
        int[] solOpt={1,49,32,45,19,41,8,9,10,43,33,51,11,52,14,13,47,26,27,28,12,25,4,6,15,5,24,48,38,37,40,39,36,35,34,44,46,16,29,50,20,23,30,2,7,42,21,17,3,18,31,22};
        
        double distOpt=0.0;
        for (int j = 0; j < solOpt.length - 1; ++j) {
            distOpt += dist[solOpt[j] - 1][solOpt[j + 1] - 1];
        }
        distOpt += dist[solOpt[solOpt.length - 1] - 1][solOpt[0] - 1];
        System.out.println("Distancia =" + distOpt);
        

        boolean cambiar=false;
        double grafoMin = distancia;
        double nuevaDist = distancia;
        int arcosCambiar[] = new int[4];
        for (int j = 0; j < solucion.length - 2; ++j) {
            int arco1_nodo1 = solucion[j];
            int arco1_nodo2 = solucion[j+1];
            for (int k = j + 2; k < solucion.length - 1; ++k) {
                int arco2_nodo1 = solucion[k];
                int arco2_nodo2 = solucion[k + 1];
                double grafoND = grafoMin + (dist[arco1_nodo1 - 1][arco2_nodo1 - 1] + dist[arco1_nodo2 - 1][arco2_nodo2 - 1]) - (dist[arco2_nodo1 - 1][arco2_nodo2 - 1] + dist[arco1_nodo1 - 1][arco1_nodo2 - 1]);
                if (grafoND < nuevaDist) {
                    nuevaDist = grafoND;
                    arcosCambiar[0] = j;
                    arcosCambiar[1] = j+1;
                    arcosCambiar[2] = k;
                    arcosCambiar[3] = k+1;
                    cambiar=true;
                }
            }
            if (j > 0) {
                int arco2_nodo1 = solucion[solucion.length - 1];
                int arco2_nodo2 = solucion[0];
                double grafoND = grafoMin + (dist[arco1_nodo1 - 1][arco2_nodo1 - 1] + dist[arco1_nodo2 - 1][arco2_nodo2-1]) - (dist[arco2_nodo1 - 1][arco2_nodo2 - 1] + dist[arco1_nodo1 - 1][arco1_nodo2 - 1]);
                if (grafoND < nuevaDist) {
                    nuevaDist = grafoND;
                    arcosCambiar[0] = j;
                    arcosCambiar[1] = j+1;
                    arcosCambiar[2] = solucion.length-1;
                    arcosCambiar[3] = 0;
                    cambiar=true;
                }
            }
        }
        System.out.println(nuevaDist);
        for (int i = 0; i < arcosCambiar.length; i++) {
            System.out.println(solucion[arcosCambiar[i]]);
        }
System.out.println("");
    }
}
